/**
 * 二分法查找
 * 递归  代码逻辑好
 * 非递归   性能更好
 * 时间复杂度O(logn)
 * 
 */


/**
 * @description 使用循环
 */

const binarySearch = (array:number[],target:number):number=>{
    if(array.length === 0) return -1
    let startIndex = 0
    let endIndex = array.length - 1

    while(startIndex <= endIndex){
        const middleIndex = Math.floor((startIndex + endIndex)/2)
        const midValue = array[middleIndex]
        if(target < midValue){
            endIndex = middleIndex - 1
        }else if (target > midValue){
            startIndex = middleIndex + 1
        }else{
            return middleIndex
        }
    }

    return -1
}

/**
 * @description  使用递归
 */
const binarySearch2 = (array:number[],target:number,startIndex?:number,endIndex?:number):number=>{
    const length = array.length
    if(length == 0) return -1
    if(startIndex == null)  startIndex = 0
    if(endIndex == null)  endIndex = length - 1
    if(startIndex > endIndex) return -1

    const middleIndex = Math.floor((startIndex + endIndex)/2)
    const middleValue = array[middleIndex]
    console.log(target,middleValue,middleIndex)
    if(target < middleValue){
       return binarySearch2(array,target,startIndex,middleIndex - 1)
    }else if (target > middleValue){
       return binarySearch2(array,target,middleIndex + 1 ,endIndex)
    }else{
        console.log('middleIndex',middleIndex)
        return middleIndex
    }
}

//凡是有序的数组   用二分法进行 时间复杂度O(logN)

// 测试
const arrbinary = [1, 2, 3, 4, 5, 6, 7];
console.log(binarySearch2(arrbinary, 5)); // 输出: 4


// const arrbinary = [1,2,3,4,55,6,7]
// const index = binarySearch2(arrbinary,55)
// console.log(index)